n,m,T=map(int,input().split())
graph_a=[[] for _ in range(n+1)]
graph_b=[[] for _ in range(n+1)]
double_graph_a=[[0]*(n+1) for _ in range(n+1)]
double_graph_b=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
u,v,t=map(int,input().split())
graph_a[v].append(u)
graph_b[v].append(t)
if u==1:
double_graph_a[v][2]=t
double_graph_b[v][2]=1
next_n=n+1
for c in range(3,next_n):
for v in range(2,next_n):
for i,nx in enumerate(graph_a[v]):
if double_graph_a[nx][c-1]:
dist=double_graph_a[nx][c-1]+graph_b[v][i]
if dist<=T and (not double_graph_a[v][c] or double_graph_a[v][c]>dist):
double_graph_a[v][c]=dist
double_graph_b[v][c]=nx
for i in range(n,0,-1):
if double_graph_b[n][i]:
break
res=[n]
while double_graph_b[res[-1]][i]!=1:
res.append(double_graph_b[res[-1]][i])
i-=1
res+=[1]
print(len(res))
print(" ".join(map(str,res[::-1])))
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
// #define int long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a,b,sizeof(a))
#define goog(tno) cout << "Case #" << tno <<": "
#define vi vector<int>
#define vii vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define in(a) for(auto &x: a)cin>>x;
#define out(a) for(auto x: a){cout<<x<<' ';}cout<<'\n';
#define inf 1e9+10
//#define mm 1000000007 998244353
void print(bool n){if(n)cout<<"YES";else cout<<"NO";cout<<'\n';}
vector<pii> adj[5000];
int p[5000][5000];
int n;
int dp[5000][5000];
int fun(int i,int j){
if(i==n-1)return (j==0)?0:inf;
if(j==0)return inf;
if(dp[i][j]!=-1)return dp[i][j];
int ans=inf;
for(auto u: adj[i]){
int x=u.se+fun(u.fi,j-1);
if(x<ans){
ans=x;
p[i][j]=u.fi;
}
}
return dp[i][j] = ans;
}
signed main(){
fastio
int m,t;
cin>>n>>m>>t;
fill(dp,-1);
rep(i,0,m){
int u,v,x;
cin>>u>>v>>x;
--u,--v;
adj[u].emplace_back(v,x);
}
int l;
rep(i,0,n){
if(fun(0,i)<=t)l=i;
}
cout<<l+1<<'\n';
int x=0;
while(l){
cout<<x+1<<' ';
x=p[x][l];
l--;
}
cout<<x+1;
return 0;
}1424M - Ancient Language | 600C - Make Palindrome |
1669D - Colorful Stamp | 1669B - Triple |
1669A - Division | 1669H - Maximal AND |
1669E - 2-Letter Strings | 483A - Counterexample |
3C - Tic-tac-toe | 1669F - Eating Candies |
1323B - Count Subrectangles | 991C - Candies |
1463A - Dungeon | 1671D - Insert a Progression |
1671A - String Building | 1671B - Consecutive Points Segment |
1671C - Dolce Vita | 1669G - Fall Down |
4D - Mysterious Present | 1316B - String Modification |
1204A - BowWow and the Timetable | 508B - Anton and currency you all know |
1672A - Log Chopping | 300A - Array |
48D - Permutations | 677C - Vanya and Label |
1583B - Omkar and Heavenly Tree | 1703C - Cypher |
1511C - Yet Another Card Deck | 1698A - XOR Mixup |